package leetcode;

import com.sun.javafx.binding.StringFormatter;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;
import java.util.concurrent.locks.Condition;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2021/4/29

*/
class MedianFinder {
    Queue<Integer> A;
    Queue<Integer> B;

    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((v1,v2)->v2-v2);
    }

    public void addNum(int num) {
        if(A.size() != B.size()){
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }

    public double findMedian() {
        if(A.size() == B.size()) return (double) (A.peek() + B.peek())/2;
        else return A.peek();
    }

    public static void main(String[] args) {
        MedianFinder m = new MedianFinder();
        System.out.println(m.findMedian());
        m.addNum(1);
        System.out.println(m.findMedian());
        m.addNum(2);
        System.out.println(m.findMedian());
        m.addNum(3);
        System.out.println(m.findMedian());

    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class solution {

    public static void main(String[] args) {
        //[1,6,3,2,5]
        int[] postorder = {1,3,2,6,5};
        solution solution = new solution();
        System.out.println((char)(25 + 97));
        //   5
        //             / \
        //            4   8
        //           /   / \
        //          11  13  4
        //         /  \    / \
        //        7    2  5   1

      /* TreeNode root = new TreeNode(5);
       TreeNode n2 = new TreeNode(4);
       TreeNode n3= new TreeNode(8);
       TreeNode n4 = new TreeNode(11);
       TreeNode n5 = new TreeNode(13);
       TreeNode n6 = new TreeNode(4);
       TreeNode n7 = new TreeNode(7);
       TreeNode n8 = new TreeNode(2);
       TreeNode n9 = new TreeNode(5);
       TreeNode n10 = new TreeNode(1);
       root.left = n2;root.right = n3; n2.left = n4;n3.left = n5;n3.right = n6; n4.left = n7;n4.right = n8;n6.left = n9;n6.right = n10;
       solution.pathSum(root,22);
      ////head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
        Node n1 = new Node(7);
        Node n2 = new Node(13);
        n1.next = n2;
        Node n3 = new Node(11); n2.next = n3;Node n4 = new Node(10); n3.next = n4;Node n5 = new Node(1);n4.next = n5;
        n2.random = n1;n3.random = n5;n4.random = n3;n5.random = n1;

        solution.copyRandomList(n1);*/
      String s = "abaccdeff";
        System.out.println(solution.firstUniqChar(s));
        int [] nums = {7,5,6,4};
        System.out.println(solution.reversePairs(nums));
    }
    int r = 0;
    public int reversePairs(int[] nums) {
        if(nums.length < 2) return 0;
        if(nums[0]>nums[1]) r++;
        for (int i = 2; i < nums.length; i++) {
            bigger(nums, i);
        }
        return r;


    }
    public void bigger(int[] nums,int pos){
        for (int i = 0; i < pos; i++) {
            if (nums[pos] < nums[i]) r++;
        }
    }

    public char firstUniqChar(String s) {
        if("".equals(s)) return ' ';
        Set<Character> set = new HashSet<>();
       Deque<Character> queue = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if(!queue.contains(c)&&!set.contains(c)){
                queue.addLast(c);
                set.add(c);
            }else{
                queue.remove(c);
            }
        }
        return queue.isEmpty()? ' ' : queue.removeFirst();
    }

    public int nthUglyNumber(int n) {
        Queue<Long> queue = new PriorityQueue<>();
        Set<Long> set = new TreeSet<>();
        set.add(1L);
        queue.offer(1L);
        int cur = 0;
        for (int i = 0; i < n; i++) {
            long tmp = queue.poll();
            cur = (int) tmp;
            if(set.add(tmp * 2)){
                queue.offer(tmp * 2);
            }
            if(set.add(tmp * 3)){
                queue.offer(tmp * 3);
            }
            if(set.add(tmp * 5)){
                queue.offer(tmp * 5);
            }

        }
        return cur;
    }
    //97
    public int translateNum(int num) {
        int before = 0, cur = 0, res = 1;
        for(int i = 0; i < String.valueOf(num).length();i++){
            before = cur;
            cur = res;
            res = 0;
            res += cur;
            if (i == 0) {
                continue;
            }
            String sub = (String.valueOf(num).substring(i - 1,i + 1));
            if(Integer.valueOf(sub) >= 10 && Integer.valueOf(sub) <= 25){
                res += before;
            }
        }
        return res;
    }

    public void quickSort(int i,int j,int[] nums){
        int left = i;
        int right = j;
        int pivot = (i + j) / 2;
        while (left < right){
            while(nums[left] < nums[pivot]){
                left ++ ;
            }
            while (nums[right] > nums[pivot]){
                right --;
            }
            if(left >= right){
                break;
            }
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            if(nums[left] == nums[pivot]){
                right --;
            }
            if(nums[right] == nums[pivot]){
                left ++;
            }
            if(left == right){
                left ++;
                right --;
            }
            if(left < j){
                quickSort(left,j,nums);
            }
            if(right > i){
                quickSort(i,right,nums);
            }
        }

    }

    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(str,(x,y)->(x + y).compareTo(y + x));
        StringBuilder sb = new StringBuilder();
        for (String s : str) {
            sb.append(s);
        }
        return sb.toString();
    }

    public int maxSubArray(int[] nums) {
        int res = nums[0];
        ("" + res).contains("1");
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i-1],0);
            res = Math.max(res,nums[i]);
        }
        return res;
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        //队列层次遍历
        Deque<TreeNode> queue = new LinkedList<>();
        List<String> res = new LinkedList<>();
        if(root != null){
            queue.addLast(root);
            res.add(root.val+"");
        }
        while(!queue.isEmpty()){
            for (int i = queue.size() - 1; i >= 0 ; i--) {
                TreeNode poll = queue.removeFirst();
                if(poll.left != null) {
                    res.add(poll.left.val + "");
                    queue.addLast(poll.left);
                }
                else res.add("null");
                if(poll.right!= null){
                    res.add(poll.right.val + "");
                    queue.addLast(poll.right);
                }
                else res.add("null");
            }
        }
        for (int i = res.size() - 1; i >= 0 ; i--) {
            if(!"null".equals(res.get(i))){
                break;
            }else {
                res.remove(i);
            }
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.replace("[", "").replace("]", "").replace(" ","").split(",");
        int i = 0,j = 1;
        Map<Integer,TreeNode> map = new HashMap<>();
        TreeNode root = null;
        if(split.length > 0){
            if(split[i] != null && !"".equals(split[i])){
                root = new TreeNode(Integer.valueOf(split[i]));
                map.put(i,root);
            }else{
                return null;
            }

        }
        while(j < split.length){
            TreeNode treeNode = map.get(i++);
            if(treeNode != null){
                if(j < split.length && !"null".equals(split[j])){
                    TreeNode left = new TreeNode(Integer.valueOf(split[j]));
                    map.put(j,left);
                    treeNode.left = left;
                }
                j++;
                if(j < split.length &&!"null".equals(split[j])){
                    TreeNode right = new TreeNode(Integer.valueOf(split[j]));
                    map.put(j,right);
                    treeNode.right = right;
                }
                j++;
            }
        }
        return root;
    }

    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head.next;
        Node root = new Node(head.val);
        Node res = root;
        map.put(head,root);
        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            root.next = node;
            root = root.next;
            cur = cur.next;
        }
        Node tmp = head;
        while(tmp != null){
            if(tmp.random != null){
                Node node = map.get(tmp);
                Node node1 = map.get(tmp.random);
                node.random = node1;
            }
            tmp = tmp.next;
        }

        return res;
    }

    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target,0,new LinkedList<>());
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    public void dfs(TreeNode root,int target,int cur,LinkedList<Integer> list){
        if(root == null) {
            return;
        }
        cur += root.val;
        list.addLast(root.val);
        if( root.left == null && root.right == null && cur == target){
            res.add(new ArrayList<>(list));
        }
        dfs(root.left,target,cur,list);
        dfs(root.right,target,cur,list);
        list.removeLast();


    }


    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while(!queue.isEmpty()){
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i= 0 ; i < queue.size();i++){
                TreeNode treeNode = queue.removeFirst();
                if((list.size() & 1 )== 0){
                    tmp.addLast(treeNode.val);
                }else{
                    tmp.addFirst(treeNode.val);
                }
                if(treeNode.left != null) queue.addLast(treeNode.left);
                if(treeNode.right != null) queue.addLast(treeNode.right);
            }
            list.add(tmp);
        }
        return list;
    }

    public  int[] levelOrders(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while(!queue.isEmpty()){
            TreeNode treeNode = queue.removeFirst();
            list.add(treeNode.val);
            if(treeNode.left!= null) queue.addLast(treeNode.left);
            if(treeNode.right != null) queue.addLast(treeNode.right);
        }
        int[] res = new int[list.size()];
        int i = 0;
        for (Integer integer : list) {
            res[i++] = integer;
        }
        return res;
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> in = new Stack<>();
        int i = 0;
        for (int push : pushed) {
            in.push(push);
            while(!in.isEmpty() && in.peek() == popped[i]){
                in.pop();
                i++;
            }
        }

        return false;

    }
}
